1. Field of Invention
The present invention relates generally to methods and apparatus for improving the performance of software applications. More particularly, the present invention relates to methods and apparatus for reducing the overhead associated with performing memory allocation.
2. Description of the Related Art
The amount of available memory is typically limited in computing systems such as object-based computing systems. Hence, memory must generally be conserved and recycled. Many computer programming languages enable software developers to dynamically allocate memory within a computer system. Some programming languages require explicit manual deallocation of previously allocated memory, which may be complicated and prone to error. Languages which require explicit manual memory management include the C and C++ programming languages. Other programming languages utilize automatic storage-reclamation to reclaim memory that is no longer necessary to ensure the proper operation of computer programs which allocate memory from the reclamation system. Such automatic storage-reclamation systems reclaim memory without explicit instructions or calls from computer programs which were previously utilizing the memory.
In object-oriented or object-based systems, the typical unit of memory allocation is commonly referred to as an object or a memory object, as will be appreciated by those skilled in the art. Objects which are in use are generally referred to as xe2x80x9clivexe2x80x9d objects, whereas objects which are no longer needed to correctly execute computer programs are typically referred to as xe2x80x9cgarbagexe2x80x9d objects or xe2x80x9cdeadxe2x80x9d objects. The act of reclaiming garbage objects is commonly referred to as garbage collection, while an automatic storage-reclamation system is often referred to as a garbage collector. Computer programs which use automatic storage-reclamation systems are known as mutators due to the fact that such computer programs are capable of changing live memory objects during execution. Computer programs written in languages such as the Java(trademark) programming language (developed by Sun Microsystems, Inc. of Palo Alto, Calif.) and the Smalltalk programming language use garbage collection to automatically manage memory.
Generally, to reduce the computational burden associated with garbage collection, a managed memory area is divided into smaller sections to enable garbage collection to be performed locally in one area at a time. One memory partitioning scheme is generational garbage collection. In generational garbage collection, objects are separated based upon their lifetimes as measured from the time the objects were created. Generational garbage collection is described in more detail in Garbage Collection: Algorithms for Automatic Dynamic Memory Management by Richard Jones and Rafael Lins (John Wiley and Sons Ltd., 1996), which is incorporated herein by reference in its entirety. xe2x80x9cYoungerxe2x80x9d objects have been observed as being more likely to become garbage than xe2x80x9colderxe2x80x9d objects. As such, generational garbage collection may be used to increase the overall efficiency of memory reclamation.
FIG. 1 is a diagrammatic representation of an area of computer memory which contains objects and is suitable for generational garbage collection. A managed area of memory 102, which is typically a heap associated with a computer system, is divided into a new generation 104 and an old generation 106. New generation 104 contains recently created objects 110, e.g., objects 110a-110e, while old generation 106 contains objects 110 which were created less recently, e.g., objects 110f and 110g. When an object 110 is to be created in memory 102, the object is created in new generation 104. In the event that new generation 104 becomes full to the extent that a new object 110 may not be allocated in new generation 104, a scavenging garbage collection may be performed on new generation 104 to free memory space.
In general, an object 110 may be referenced by other objects 110. By way of example, object 110b has a pointer 114a to object 110a. As will be understood by one of skill in the art, object 110b may be considered to be live when a root points to object 110b transitively. That is, when object 110b is pointed to by a list of pointers which, in turn, is identified by a root, then object 110b is considered to be live.
When new generation object 110d is live and points to old generation object 110f, garbage collection performed in old generation 106 does not generally xe2x80x9ccollectxe2x80x9d object 110f, since object 110f is referenced by a live object. However, if new generation object 110d is dead, a garbage collection performed in new generation 104 may result in old generation object 110f becoming unreachable if old generation object 110f is not be pointed to by any other object. If old generation object 110f is unreachable, then garbage collection performed in old generation 106 will result in the collection of old generation object 110f. When a pointer 114b points from new generation object 110d to old generation object 110f, old generation object 110f is considered to be tenured garbage, as old generation object 110f is not collectable using new generation garbage collection, i.e., a garbage collection performed on new generation 104.
During a scavenging garbage collection process performed on new generation 104 when new generation 104 becomes full, as will be discussed below with respect to FIG. 2, live objects 110 in new generation 104 are copied from new generation 104 into old generation 106. Newly allocated objects 110 in new generation 104 are often live and, hence, must be copied from new generation 104 into old generation 106 during a scavenging garbage collection. In general, copying operations are slow and expensive. As a result, the overall garbage collection process is expensive.
Some generational garbage collectors copy live objects from a new generation into an intermediate area before the objects are tenured to an old generation. FIG. 1b is a diagrammatic representation of a memory space which is divided into a new generation, an intermediate area, and an old generation. A memory space 202 includes a new generation 204, a xe2x80x9cfrom-spacexe2x80x9d and xe2x80x9cto-spacexe2x80x9d 205, and an old generation 206. Newly allocated objects 210 are allocated in new generation 204. When new generation 204 becomes full, live objects 210 are copied out of new generation 204 and into from-space and to-space 205. Objects 210 are allowed to remain in from-space and to-space 205 for some period of time, e.g., for a predetermined amount of time or until from-space and to-space 205 is full, to enable objects 210 in from-space and to-space 205 to die. Periodically, as for example when from-space and to-space 205 is full, a garbage collection is performed on from-space and to-space 205. During garbage collection on from-space and to-space 205, live objects in from-space and to-space 205 are copied into, or tenured to, old generation 206.
With reference to FIG. 2, one conventional method of performing a scavenging garbage collection on a managed area of memory which is divided into a new generation and an old generation, e.g., managed area 102 of FIG. 1, will be described. Specifically, a process of performing a scavenging garbage collection on a new generation will be discussed. A process 252 of performing a garbage collection begins at step 256 in which a list of live objects in the new generation is obtained. A list of live objects may be obtained using a variety of different methods. For example, one method which may be used to obtain a list of live objects involves studying global objects, or roots, which reference objects within either or both a new generation and an old generation to identify objects which are currently in use.
After a list of live objects is obtained, a live object identified in the list is obtained from the new generation in step 258. During a scavenging garbage collection, live objects in the new generation are generally copied into the old generation in an effort to free memory space in the new generation. Hence, in step 260, the live object is copied to the old generation. As should be understood by those skilled in the art, copying a live object into the old generation includes copying objects referenced by the live object, in addition to changing any pointers which identify the live object such that the pointers instead identify the copy of the object. Further, copying the live object from the new generation into the old generation effectively frees memory space in the new generation, which was associated with the live object, for other uses.
Once the live object is copied into the old generation in step 260, a determination is made in step 262 as to whether there are additional live objects remaining in the new generation. That is, it is determined if there are more live objects identified in the list of live objects. When it is determined that there are additional live objects in the list of live objects, then process flow returns to step 258 where the next live object identified in the list is obtained. Alternatively, when there are no additional live objects in the new generation, the indication is that there are no live objects remaining in the new generation, and the process of performing a scavenging garbage collection on the new generation is completed.
A scavenging garbage collection is often an expensive process. Specifically, as mentioned above, the copying of a live object during a scavenging garbage collection is a slow and expensive operation. Hence, when many live objects are copied during a scavenging garbage collection, or when a few large objects are copied during a scavenging garbage collection, the garbage collection process itself becomes both slow and costly.
Therefore, what is desired is a method for reducing the cost associated with a generational scavenging garbage collection. That is, what is needed is a method and apparatus for reducing the number of live objects copied to an old generation during a generational scavenging garbage collection.
The present invention relates to a memory space which enables an efficient generational scavenging garbage collection to be performed. According to one aspect of the present invention, a method for reclaiming memory space uses a managed memory area that includes a first area and a second area. The first area is arranged to store recently allocated objects when the first area has available memory space, while the second area being arranged to store older objects. The method includes determining when a first section of the first area in which new objects are to be allocated is substantially filled. When it is determined that the first section is substantially filled, a garbage collection is performed on a second section of the first. After the garbage collection, the second section is set to support new object allocation such that new objects are allocated in the second section, while the first section is reset such that it is no longer arranged to support new object allocation. In one embodiment, performing the garbage collection on the second section includes copying a live object from the second section into the second area.
In another embodiment, the method also includes attempting to allocate a new object in the second section after the second section is set to support new object allocation, and determining when the second section is substantially filled. When it is determined that the second section is not substantially filled, a new object is allocated in the second section. Alternatively, when it is determined that the second section is substantially filled, a garbage collection is performed on the first section. In such an embodiment, when determined that the second section is substantially filled, the method may further include resetting the second section such that the second section is no longer arranged to support new object allocation, resetting the first section such that the first section is once again arranged to support new object allocation, and allocating the new object in the first section.
According to another aspect of the present invention, a computer system for reclaiming memory space in a managed memory area that includes a first area and a second area includes a processor and a determinator for determining when a first section of the first area, which supports new object allocation, is substantially filled. The system also includes a garbage collector that scavenges a second section of the first area when it is determined that the first section is substantially filled, in addition to a tracking mechanism arranged to set the second section such that the second section is arranged to support new object allocation and to set the first section such that the first section is no longer arranged to support new object allocation. In one embodiment, the first section and the second section are separated by a boundary, and the system additionally includes an adjuster for altering the relative sizes of the first section and the second section by moving the boundary.
According to still another aspect of the present invention, a memory structure that stores objects in a computer system includes a first area and a second area. The first area is effectively partitioned into a first section, which may store a recently allocated object, and a second section, which may store a first object allocated before the recently allocated object. When the first section is full, the second section is arranged to undergo a garbage collection. The second area of the memory structure stores a second object that was allocated prior to the allocation of the first object. In one embodiment, the second area is further arranged to store a copy of the first object when a garbage collection is performed on the second section. In such an embodiment, when the second section undergoes the garbage collection, the second section is then used to store a third object which is allocated at some point after the allocation of the recently allocated object.